#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    MAX = 1234567890

    def coinChange(self, coins, amount):
        # write your code here
        if amount == 0:
            return 0

        self.coins = coins
        self.coins.sort()
        self.coins = [e for e in self.coins if e != 0]      # out '0' coin

        # print(self.coins)
        self.hash = {}  # {amount : min_number}
        # self.hash

        for coin in self.coins:
            self.hash[coin] = 1

        ret = self.rec_change(amount)
        if ret >= self.MAX:
            return -1
        else:
            return ret

    def rec_change(self, amount):
        num = self.hash.get(amount)
        if num is not None:
            return num

        least = self.MAX

        for coin in self.coins:
            if amount < coin:
                break

            least = min(least, self.rec_change(amount-coin) + 1)

        self.hash[amount] = least
        return least


def main():
    print("start main")
    s = Solution()
    # ret = s.coinChange([1,2,5], 11)
    ret = s.coinChange([0, 1], 0)
    print(ret)

if __name__ == "__main__":
    main()
